package java2;

import java.util.Arrays;
import java.util.Scanner;

public class Q1bufenzq {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int[] digits = null;
		String str;
		int digit;
		while (sc.hasNextLine()) {
			String choice = sc.nextLine();	
			if(choice.equals("fib")) {
				int n = Integer.parseInt(sc.nextLine());
				fib(n);
				str = sc.nextLine();
			}
			else if(choice.equals("sort")) {
				String[] strDigits =sc.nextLine().split(" ");
				digits = new int[strDigits.length];
				for (int i = 0; i < strDigits.length; i++) {
					digits[i] = Integer.parseInt(strDigits[i]);
				}
				Arrays.sort(digits);
				System.out.println(Arrays.toString(digits));
			}
			else if(choice.equals("search")) {
				digit = sc.nextInt();
				str = sc.nextLine();
				int pos = Arrays.binarySearch(digits, digit);
				if (pos < 0)
					System.out.println(-1);
				else
					System.out.println(Arrays.binarySearch(digits, digit));
			}
			else if(choice.equals("getBirthDate")) {
				int x = Integer.parseInt(sc.nextLine());
				for (int i=0; i < x; i++) {
					String id = sc.nextLine();
					String year=id.substring(6, 10);
					String month=id.substring(10, 12);
					String day=id.substring(12, 14);
					System.out.println(year+"-"+month+"-"+day);
				}
			
			}
			else {
				System.out.println("exit");
			}
		}

	}

	private static void fib(int n) {
		int[] fib = new int[100]; 
		fib[1]=1;
		fib[2]=1;
		for (int i=3; i <= n; i++) {
			fib[i] = fib[i-1] + fib[i-2];
		}
		for (int j = 1; j < n; j++) 
			System.out.printf(fib[j] + " ");
		System.out.println(fib[n]);
	}
}
